package conclusion;

import java.util.Stack;

import leetCode.LeetCode_day11_tree;

import data_structure.BTNode;

public class Tree {
	
	public static void boundaryTraversal(BTNode root){
		//left boundary
		BTNode ind = root, pre = null;
		while(ind != null){
			if(pre != null)
				System.out.print(pre.val + ", ");
			pre = ind;
			ind = ind.left;
		}
		//all leaves
		printLeaves(root);
		//right boundary
		if(root.right != null){
			ind = root.right; pre = null;
			Stack<BTNode> s = new Stack<BTNode>();
			while(ind != null){
				if(pre != null) s.push(pre);
				pre = ind;
				ind = ind.right;
			}
			
			while(!s.isEmpty()){
				ind = s.pop();
				System.out.print(ind.val + ", ");
			}
		}
	}
	
	private static void printLeaves(BTNode root){
		if(root != null){
			printLeaves(root.left);
			if(root.left == null && root.right == null)
				System.out.print(root.val + ", ");
			printLeaves(root.right);
		}
	}
	
	/**
	 * Button up
	 * @param root
	 * @return
	 */
	public static BTNode mirrorOfTree(BTNode root){
		if(root == null) return null;
		BTNode left = mirrorOfTree(root.right);
		BTNode right = mirrorOfTree(root.left);
		root.left = left; root.right = right;
		return root;
	}
	
	public static BTNode mirrorOfTree1(BTNode root){
		if(root == null) return null;
		Stack<BTNode> s = new Stack<BTNode>();
		s.push(root);
		while(!s.isEmpty()){
			BTNode node = s.pop();
			if(node.left != null) s.push(node.left);
			if(node.right != null) s.push(node.right);
			BTNode t = node.left;
			node.left = node.right;
			node.right = t;
		}
		return root;
	}
	
	
	public static void main(String[] args) {
		BTNode root = LeetCode_day11_tree.constructBSTFromSortedArray(new int[]{1,2,3,4,5,6,7,8}, 0, 7);
		boundaryTraversal(root);
		System.out.println();
		LeetCode_day11_tree.binaryTreeLevelOrderTraversal(root);
		System.out.println();
		LeetCode_day11_tree.binaryTreeLevelOrderTraversal(mirrorOfTree(root));
		System.out.println();
		LeetCode_day11_tree.binaryTreeLevelOrderTraversal(mirrorOfTree1(root));
	}

}
